//
// Created by Crestimes on 2024/11/18.
//

#include "FABuilder.h"

#include <algorithm>
#include <iomanip>
#include <queue>
#include <stack>
#include <sstream>

#include "global.h"
#include "ReManager.h"

FABuilder::FABuilder(map<string, string> &reMap,
                     set<string> &symbols,
                     size_t &NFAStart,
                     size_t &DFAStart,
                     size_t &MinDFAStart,
                     set<size_t> &NFAEnds,
                     set<size_t> &DFAEnds,
                     set<size_t> &MinDFAEnds,
                     vector<NFANode> &NFANodes,
                     map<size_t, map<string, size_t>> &DFANodes,
                     map<size_t, map<string, size_t>> &MinDFANodes,
                     map<string, pair<map<size_t, map<string, size_t>>, set<size_t>>> &DFAsAndEndsOfTokenType,
                     map<string, pair<map<size_t, map<string, size_t>>, set<size_t>>> &DFAsAndEndsOfAuxiliary,
                     set<string> &reOfTokenType,
                     set<string> &reForAuxiliary)
    : DFAsAndEndsOfTokenType(DFAsAndEndsOfTokenType),
      DFAsAndEndsOfAuxiliary(DFAsAndEndsOfAuxiliary),
      reMap(reMap),
      reOfTokenType(reOfTokenType),
      reForAuxiliary(reForAuxiliary),
      symbols(symbols),
      NFAEnds(NFAEnds),
      NFAStart(NFAStart),
      DFAEnds(DFAEnds),
      DFAStart(DFAStart),
      MinDFAEnds(MinDFAEnds),
      MinDFAStart(MinDFAStart),
      NFANodes(NFANodes),
      finalNFA(0, 0),
      DFANodes(DFANodes),
      MinDFANodes(MinDFANodes)
{
    // [GUI CHANGES] 修改构造函数实现
    // this->reMap = reMap;
    //    buildDFAs();
}

/**
 * [GUI CHANGES] 根据传入的正则名构建对应的自动机
 * @param reName 正则名
 */
void FABuilder::buildDFAs(const string &reName)
{
    // [GUI CHANGES] 单独构造每个正则的自动机而不是循环一次构造完成
    clear(); // [GUI CHANGES] 清空数据操作提前
             // 初始化成员变量
    initBeforeGenerate(reName);
    // 获取NFA图
    generateNFA();
    // 打印结果NFA图
    printNFAMatrix();
    // 由NFA图得到DFA图
    generateDFA();
    // 打印结果DFA图
    printDFAMatrix();
    // 最小化DFA
    minimizeDFA();
    // 打印最小化DFA图
    printMinDFAMatrix();
    // 保存DFA图
    if (reOfTokenType.count(reName))
    {
        DFAsAndEndsOfTokenType[reName] = make_pair(MinDFANodes, MinDFAEnds); // [GUI CHANGES] 最后的终点集是MinDFA的终点集
    }
    else
    {
        DFAsAndEndsOfAuxiliary[reName] = make_pair(MinDFANodes, MinDFAEnds); // [GUI CHANGES] 最后的终点集是MinDFA的终点集
    }
    //    // 清空数据
    //    clear(); // [GUI CHANGES] 清空操作提前
}

void FABuilder::initBeforeGenerate(const string &reName)
{
    // 初始化通用成员变量
    this->reNameNow = reName;
    this->reValueNow = reMap[reName];
    cout << "reName: " << this->reNameNow << endl;
    cout << "reValue: " << this->reValueNow << endl;
}

void FABuilder::generateNFA()
{
    // 转后缀表达式
    initSuffixRe();
    // 计算后缀表达式
    calcSuffixRe();
}

/**
 * 将正则表达式转为后缀形式，保存到suffixRe成员变量
 */
void FABuilder::initSuffixRe()
{
    for (size_t i = 0; i < reValueNow.length(); i++)
    {
        if (reValueNow[i] == '\\')
        {
            if (reValueNow[i + 1] == 'n')
            {
                // 换行符，特殊处理
                suffixRe.emplace(1, '\n');
                // 保存字符
                symbols.insert("\n");
            }
            else
            {
                // 转义符号，字符入后缀表达式
                suffixRe.push(string("\\") + reValueNow[i + 1]);
                // 保存字符
                symbols.emplace(1, reValueNow[i + 1]);
            }
            i++; // 跳过下一个字符
        }
        else if (ReManager::isOpr(reValueNow[i]))
        {
            // 运算符，需要判断优先级
            // 进行出栈操作，直到优先级不大于自己
            if (reValueNow[i] == '|')
            {
                while (!oprStack.empty() && oprStack.top() != '(' && oprStack.top() != '|')
                {
                    suffixRe.emplace(1, oprStack.top());
                    oprStack.pop();
                }
            }
            else if (reValueNow[i] == '&')
            {
                while (!oprStack.empty() && oprStack.top() != '(' && oprStack.top() != '|' && oprStack.top() != '&')
                {
                    suffixRe.emplace(1, oprStack.top());
                    oprStack.pop();
                }
            }
            // '*' '+' '?'
            oprStack.push(reValueNow[i]);
        }
        else if (reValueNow[i] == ')')
        {
            // 将栈中的符号出栈，直到遇到左括号
            while (!oprStack.empty() && oprStack.top() != '(')
            {
                suffixRe.emplace(1, oprStack.top());
                oprStack.pop();
            }
            oprStack.pop(); // 弹出(
        }
        else if (reValueNow[i] == '(')
        {
            // ( 直接入栈
            oprStack.push(reValueNow[i]);
        }
        else
        {
            // 字符直接入后缀表达式
            // 可能是某个正则名，需要遍历判断
            bool isReName = false;
            for (const auto &auxRe : reForAuxiliary)
            {
                if (i + auxRe.length() - 1 < reValueNow.length() && reValueNow.substr(i, auxRe.length()) == auxRe)
                {
                    // 整个是一个正则名
                    isReName = true;
                    suffixRe.emplace(auxRe);
                    // 保存字符（正则名）
                    symbols.insert(auxRe);
                    // 移动下标
                    i += auxRe.length() - 1;
                    break;
                }
            }
            if (!isReName)
            {
                // 不是正则名则只放入一个字符即可
                suffixRe.emplace(1, reValueNow[i]);
                // 保存字符
                symbols.emplace(1, reValueNow[i]);
            }
        }
    }
    // 剩余符号进入后缀表达式
    while (!oprStack.empty())
    {
        suffixRe.emplace(1, oprStack.top());
        oprStack.pop();
    }
}

/**
 * 计算后缀表达式，构建NFA图
 */
void FABuilder::calcSuffixRe()
{
    while (!suffixRe.empty())
    {
        string front = suffixRe.front();
        suffixRe.pop();
        if (front[0] == '\\' || !ReManager::isOpr(front[0]))
        {
            // 是字符，直接入栈
            // 转义字符要去掉转义符号
            if (front[0] == '\\')
            {
                NFAStack.push(createNFA(front.substr(1)));
            }
            else
            {
                NFAStack.push(createNFA(front));
            }
        }
        else
        {
            // 运算符，需要进行运算
            const char op = front[front.length() - 1];
            NFA n1 = NFAStack.top();
            NFAStack.pop();
            // 双目运算符
            if (op == '|')
            {
                NFA n2 = NFAStack.top();
                NFAStack.pop();
                NFAStack.push(orCalc(n2, n1));
            }
            else if (op == '&')
            {
                NFA n2 = NFAStack.top();
                NFAStack.pop();
                NFAStack.push(andCalc(n2, n1));
            }
            // 单目运算符
            else if (op == '?')
                NFAStack.push(whatCalc(n1));
            else if (op == '*')
                NFAStack.push(mulCalc(n1));
            else if (op == '+')
                NFAStack.push(plusCalc(n1));
            // error
            else
                cout << "unexpected op: " + string(1, op);
        }
    }
    // 栈顶NFA即为结果
    finalNFA = NFAStack.top();
    NFAStack.pop();
    // 标记起点和终点集
    NFAStart = finalNFA.start;
    NFAEnds.insert(finalNFA.end);
    // ^^^[GUI CHANGES] 修改起点和终点集的保存逻辑
}

/**
 * 创建两个点并在两个点之间连线，返回这个NFA
 * @param symbolOnEdge 两个点的边上的字符
 * @return 创建的NFA
 */
NFA FABuilder::createNFA(const string &symbolOnEdge)
{
    // 创建两个NFA点
    createTwoNFANodes();
    // 连接两个点
    addNFAEdge(NFANodes.size() - 2, NFANodes.size() - 1, symbolOnEdge);
    // 创建NFA
    return {NFANodes.size() - 2, NFANodes.size() - 1};
}

/**
 * 为NFANodes列表里索引为st和ed的两点添加一条边，边值为symbolOnEdge
 * @param start 起点下标
 * @param end 终点下标
 * @param symbolOnEdge 两个点之间边上的字符
 */
void FABuilder::addNFAEdge(const size_t start, const size_t end, const string &symbolOnEdge)
{
    // 创建边
    Edge edge(start, end, symbolOnEdge);
    edges.push_back(edge);
    // 邻接表建边
    edge.next = NFANodes[start].first;
    NFANodes[start].first = &edge;
    // 记录信息用于打印
    NFANodes[start].tableMap[symbolOnEdge].push_back(end);
}

/**
 * 创建两个的NFA节点，保存到NFANodes中
 */
void FABuilder::createTwoNFANodes()
{
    NFANodes.emplace_back();
    NFANodes.emplace_back();
}

NFA FABuilder::mulCalc(const NFA &originNFA)
{
    // 创建两个点
    createTwoNFANodes();
    const size_t start = NFANodes.size() - 2;
    const size_t end = NFANodes.size() - 1;
    // 连四条线
    addNFAEdge(start, originNFA.start, EPSILON);
    addNFAEdge(start, end, EPSILON);
    addNFAEdge(originNFA.end, end, EPSILON);
    addNFAEdge(originNFA.end, originNFA.start, EPSILON);
    // 返回NFA图
    return {start, end};
}

NFA FABuilder::plusCalc(const NFA &originNFA)
{
    // 创建两个点
    createTwoNFANodes();
    const size_t start = NFANodes.size() - 2;
    const size_t end = NFANodes.size() - 1;
    // 连三条线
    addNFAEdge(start, originNFA.start, EPSILON);
    addNFAEdge(originNFA.end, end, EPSILON);
    addNFAEdge(originNFA.end, originNFA.start, EPSILON);
    // 返回NFA图
    return {start, end};
}

NFA FABuilder::whatCalc(const NFA &originNFA)
{
    // 创建两个点
    createTwoNFANodes();
    const size_t start = NFANodes.size() - 2;
    const size_t end = NFANodes.size() - 1;
    // 连三条线
    addNFAEdge(start, originNFA.start, EPSILON);
    addNFAEdge(start, end, EPSILON);
    addNFAEdge(originNFA.end, end, EPSILON);
    // 返回NFA图
    return {start, end};
}

NFA FABuilder::orCalc(const NFA &originN1, const NFA &originN2)
{
    // 创建两个点
    createTwoNFANodes();
    const size_t start = NFANodes.size() - 2;
    const size_t end = NFANodes.size() - 1;
    // 连四条线
    addNFAEdge(start, originN1.start, EPSILON);
    addNFAEdge(start, originN2.start, EPSILON);
    addNFAEdge(originN1.end, end, EPSILON);
    addNFAEdge(originN2.end, end, EPSILON);
    // 返回NFA图
    return {start, end};
}

NFA FABuilder::andCalc(const NFA &originN1, const NFA &originN2)
{
    // 直接将两个NFA连接
    addNFAEdge(originN1.end, originN2.start, EPSILON);
    return {originN1.start, originN2.end};
}

void FABuilder::generateDFA()
{
    // 初步构建DFA图
    initDFATemp();
    // 化简DFA图
    initDFA();
}

/**
 * 初步构建DFA图，每个DFA点的内容形如 { + 节点,节点... + }
 */
void FABuilder::initDFATemp()
{
    set<string> nodeStringSet; // 多个NFA节点构成的单个DFA节点，使用 { + 节点,节点... + } 的字符串标识
    // 获取初始状态集合
    set<size_t> epsilonSet = findNextE(finalNFA.start);
    queue<set<size_t>> qu;
    qu.push(epsilonSet);
    // 不断迭代
    while (!qu.empty())
    {
        set<size_t> front = qu.front();
        qu.pop();
        // 获取集合唯一标识str
        string nodeString = setToStr(front);
        if (nodeString != "{}")
            nodeStringSet.insert(nodeString);
        // 向该集合尝试所有输入
        for (const string &symbol : symbols)
        {
            set<size_t> toNodes; // 通过c最终到达的所有点
            for (const size_t i : front)
            {
                // 获取到通过c到达的所有点
                vector<size_t> toNodesTemp = NFANodes[i].tableMap[symbol];
                // 遍历所有点执行epsilon闭包
                for (size_t j : toNodesTemp)
                {
                    toNodes.insert(j);         // 加入最后的点集
                    epsilonSet = findNextE(j); // epsilon闭包
                    for (size_t k : epsilonSet)
                        toNodes.insert(k); // 加入最后的点集
                }
            }
            // 如果之前没出现过这种集合，就加入最后结果，并且入队继续迭代，否则就舍弃
            string toNodeString = setToStr(toNodes);
            if (toNodeString != "{}" && !nodeStringSet.count(toNodeString))
            {
                nodeStringSet.insert(toNodeString);
                qu.push(toNodes);
            }
            // 建立DFA图
            DFANodesTemp[nodeString][symbol] = toNodeString;
        }
    }
}

/**
 * 给DFATemp的点重新配索引，以索引为键而不是像 { + 节点,节点... + } 这样的字符串为键
 * [GUI CHANGES] 修改函数中起点和终点集的遍历和保存逻辑
 */
void FABuilder::initDFA()
{
    // 当前DFA图的所有点都是集合的字符串形式，打印出来非常多内容而且难以分析
    // 整个映射
    map<string, size_t> nodeString2Index; // 每个DFA和他对应的新点下标
    string startNodeString;               // 用来标记起点字符串，后续会更新为新起点索引
    size_t index = 1;                     // 下标从1开始（在遍历中会记录起点字符串，会把起点字符串标记为下标0，下标0即起点）
    set<size_t> newEnds;                  // 换了下标后的新的终点集
    for (const auto &oldNode : DFANodesTemp)
    {
        // 把first转成set<size_t>
        const string nodeString = oldNode.first;
        set<size_t> st = strToSet(nodeString);
        // 判断是否终点
        for (size_t end : NFAEnds)
        {
            if (st.count(end))
            {
                // 记录新的终点
                newEnds.insert(index);
            }
        }
        // 判断是否起点
        if (st.count(NFAStart))
            startNodeString = nodeString;
        nodeString2Index[nodeString] = index++;
    }
    // 起点换到下标0
    nodeString2Index[startNodeString] = 0;
    DFAStart = 0;
    // 该起点也可能是终态，需要判断是否要将新起点索引0补回到ends集合
    const set<size_t> st = strToSet(startNodeString);
    for (size_t ed : NFAEnds)
    {
        if (st.count(ed))
        {
            newEnds.insert(0);
        }
    }
    // 更新终点集
    DFAEnds = newEnds;
    // 将原DFA图中的每个点(字符串)替换成下标索引，得到新的DFA
    for (const auto &oldNode : DFANodesTemp)
    {
        map<string, size_t> newDFAMap;
        for (const auto &oldMap : oldNode.second)
        {
            // 遍历旧的转移图
            if (oldMap.second == "{}")
                continue; // 因为前面要打印所以里面加了空集，跳过空集
            // 使用nodeString2Index找到要替换的索引，更新到newDFAMap
            newDFAMap[oldMap.first] = nodeString2Index[oldMap.second];
        }
        // 该次遍历的起点也用nodeString2Index找到对应的索引，赋值上面生成的新转移图
        DFANodes[nodeString2Index[oldNode.first]] = newDFAMap;
    }
}

void FABuilder::minimizeDFA()
{
    set<size_t> visit;          // 标记是否访问过该点
    set<size_t> newEnds;        // 新终点集
    map<size_t, size_t> sameTo; // key下标的点等价于value下标的点，后续会将所有key下标的点用value值替代
    for (const auto &i : DFANodes)
    {
        if (visit.count(i.first))
            continue;
        for (const auto &j : DFANodes)
        {
            // 两重循环两两比较
            if (i.second == j.second)
            {
                // 如果转移图一模一样
                visit.insert(j.first);     // 标记已访问
                sameTo[j.first] = i.first; // j可以用i替代（first是下标索引）
                // 判断要被替代的这个j的索引是否为终态
                if (DFAEnds.count(j.first))
                {
                    // 是终态，后续被替换成的i的索引也应该是终态，在新终点集中加入i的索引
                    newEnds.insert(i.first);
                }
            }
        }
    }
    // 更新终点集
    MinDFAEnds = newEnds;
    for (const auto &node : DFANodes)
    {
        if (!MinDFANodes.count(sameTo[node.first]))
            MinDFANodes[sameTo[node.first]] = map<string, size_t>();
        for (const auto &toMap : node.second)
        {
            MinDFANodes[sameTo[node.first]][toMap.first] = sameTo[toMap.second];
        }
    }
}

/**
 * 找到下标为index的NFA点的所有通过epsilon相连的点，即求该NFA点的epsilon闭包
 * @param index 下标
 * @return 该NFA点的epsilon闭包结果
 */
set<size_t> FABuilder::findNextE(const size_t index)
{
    set<size_t> result;
    queue<size_t> qu;
    qu.push(index);
    while (!qu.empty())
    {
        size_t front = qu.front();
        qu.pop();
        result.insert(front);
        for (size_t i : NFANodes[front].tableMap[EPSILON])
            qu.push(i);
    }
    return result;
}

/**
 * {..} -> set<size_t>
 * @param setString 集合的字符串标识
 * @return 标识对应的集合
 */
set<size_t> FABuilder::strToSet(string setString)
{
    setString = setString.substr(1, setString.size() - 2); // 去除{}
    stringstream ss(setString);
    string item;
    set<size_t> st;
    while (getline(ss, item, ','))
    {
        // 分割,
        st.insert(strtol(item.c_str(), nullptr, 10));
    }
    return st;
}

/**
 * 清空数据
 * [GUI CHANGES] 修改函数中起点和终点集的置空逻辑
 */
void FABuilder::clear()
{
    set<string>().swap(symbols);
    set<size_t>().swap(NFAEnds);
    set<size_t>().swap(DFAEnds);
    set<size_t>().swap(MinDFAEnds);
    NFAStart = 0;
    DFAStart = 0;
    MinDFAStart = 0;

    stack<char>().swap(oprStack);
    stack<NFA>().swap(NFAStack);
    queue<string>().swap(suffixRe);
    vector<NFANode>().swap(NFANodes);
    vector<Edge>().swap(edges);
    finalNFA = NFA(0, 0);

    map<string, map<string, string>>().swap(DFANodesTemp);
    map<size_t, map<string, size_t>>().swap(DFANodes);

    map<size_t, map<string, size_t>>().swap(MinDFANodes);
}

/**
 * 将集合转为字符串标识，用于NFA转DFA的算法中
 * @param epsilonSet epsilon闭包的结果集合
 * @return 集合内容组成的标识字符串
 */
string FABuilder::setToStr(const set<size_t> &epsilonSet)
{
    if (epsilonSet.empty())
        return "{}";
    // 一种集合转换为唯一一种string
    // 先转成数组排序后合成字符串
    vector<size_t> ve(epsilonSet.begin(), epsilonSet.end());
    sort(ve.begin(), ve.end());
    string nodeString = "{" + to_string(ve[0]);
    for (size_t i = 1; i < ve.size(); i++)
        nodeString += ("," + to_string(ve[i]));
    return nodeString + "}";
}

void FABuilder::printNFAMatrix()
{
    symbols.insert(EPSILON);     // 打印的时候展示空，打印完成后会移除
    constexpr size_t split = 10; // 打印间隔
    cout << right << setw(split) << "NFA";
    for (const auto &symbol : symbols)
    {
        // 表头为所有存过的字符和空
        if (symbol == "\n")
            cout << right << setw(split) << "\\n";
        else
            cout << right << setw(split) << symbol;
    }
    cout << endl;
    for (size_t i = 0; i < NFANodes.size(); i++)
    {
        cout << right << setw(split) << i;
        string toNodes;
        for (const auto &symbol : symbols)
        {
            // 判断该点有没有边的值是c，有就存入边上对应的终点
            if (NFANodes[i].tableMap.count(symbol) && !NFANodes[i].tableMap[symbol].empty())
            {
                toNodes = to_string(NFANodes[i].tableMap[symbol][0]);
                for (size_t j = 1; j < NFANodes[i].tableMap[symbol].size(); j++)
                {
                    toNodes += ',';
                    toNodes += to_string(NFANodes[i].tableMap[symbol][j]);
                }
            }
            // 否则就为空
            else
            {
                toNodes = '.';
            }
            cout << right << setw(split) << toNodes;
        }
        cout << endl;
    }
    // 打印起点和终点集
    cout << right << setw(split) << "set<st>" << right << setw(split) << NFAStart << endl;
    cout << right << setw(split) << "set<ed>";
    for (const auto i : NFAEnds)
    {
        cout << right << setw(split) << i;
    }
    // ^^^[GUI CHANGES] 修改起点和终点集的遍历逻辑
    cout << endl
         << endl;
    symbols.erase(EPSILON);
}

void FABuilder::printDFAMatrix() const
{
    constexpr size_t split = 6; // 打印间隔
    cout << right << setw(split) << "DFA";
    for (const auto &symbol : symbols)
    {
        // 表头为所有存过的字符
        if (symbol == "\n")
            cout << right << setw(split) << "\\n";
        else
            cout << right << setw(split) << symbol;
    }
    cout << endl;
    for (auto node : DFANodes)
    {
        // 包含NFA的终点的就是终点
        cout << right << setw(split) << node.first;
        for (const auto &symbol : symbols)
        {
            if (node.second.count(symbol))
                cout << right << setw(split) << node.second[symbol];
            else
                cout << right << setw(split) << -1;
        }
        cout << endl;
    }
    // 打印起点和终点集
    cout << right << setw(split) << "set<st>" << right << setw(split) << DFAStart << endl;
    cout << right << setw(split) << "set<ed>";
    for (const auto i : DFAEnds)
    {
        cout << right << setw(split) << i;
    }
    // ^^^[GUI CHANGES] 修改起点和终点集的遍历逻辑
    cout << endl
         << endl;
}

void FABuilder::printMinDFAMatrix() const
{
    constexpr size_t split = 6; // 打印间隔
    cout << right << setw(split) << "MinDFA";
    for (const auto &symbol : symbols)
    {
        // 表头为所有存过的字符
        if (symbol == "\n")
            cout << right << setw(split) << "\\n";
        else
            cout << right << setw(split) << symbol;
    }
    cout << endl;
    for (auto node : MinDFANodes)
    {
        cout << right << setw(split) << node.first;
        for (const auto &symbol : symbols)
        {
            if (node.second.count(symbol))
                cout << right << setw(split) << node.second[symbol];
            else
                cout << right << setw(split) << -1;
        }
        cout << endl;
    }
    // 打印起点和终点集
    cout << right << setw(split) << "set<st>" << right << setw(split) << MinDFAStart << endl;
    cout << right << setw(split) << "set<ed>";
    for (const auto i : MinDFAEnds)
    {
        cout << right << setw(split) << i;
    }
    // ^^^[GUI CHANGES] 修改起点和终点集的遍历逻辑
    cout << endl
         << endl;
}
